import java.util.HashSet;

// 位图的实现
// 这个类Bitset是一个简单的位图数据结构的实现，用于表示一组整数的存在状态。
// 它提供了添加、删除、反转和检查元素是否存在等功能。
// Bitset(int size)：构造函数，用于创建一个指定大小的位图
// void add(int num)：将指定的数字添加到位图中，表示该数字存在
// void remove(int num)：将指定的数字从位图中移除，表示该数字不存在
// void reverse(int num)：反转指定数字在位图中的状态，如果存在则变为不存在，反之亦然
// boolean contains(int num)：检查指定的数字是否存在于位图中
public class Code01_Bitset {

    // 位图的实现
    // 使用时num不要超过初始化的大小
    public static class Bitset {
        // 用于存储位图数据的数组
        // 每个整数在位图中由数组中的一个或多个位表示
        public int[] set;

        // Bitset的构造函数，接受一个整数n，表示位图能够表示的数字范围（0到n - 1）
        public Bitset(int n) {
            // a/b如果结果想向上取整，可以写成 : (a + b - 1)/b
            // 前提是a和b都是非负数
            // 这里计算需要多少个整数来存储位图数据
            // 因为每个int类型可以存储32位，所以将总位数除以32向上取整得到所需的int数组大小
            set = new int[(n + 31) / 32];
        }

        // 将指定的数字num添加到位图中
        // 操作是通过位运算实现的
        public void add(int num) {
            // 计算num对应的位在set数组中的哪个整数中
            // num / 32得到所在的整数索引
            // 然后使用位或操作（|）将该位置为1，表示num存在
            // 1 << (num % 32) 将1左移num % 32位，对应到正确的位上
            set[num / 32] |= 1 << (num % 32);
        }

        // 将指定的数字num从位图中移除
        public void remove(int num) {
            // 同样先计算num对应的位在set数组中的位置
            // 使用位与操作（&）和取反操作（~）将该位置为0，表示num不存在
            // ~(1 << (num % 32)) 取反后的数，与原来的数进行位与操作，将对应的位清零
            set[num / 32] &= ~(1 << (num % 32));
        }

        // 反转指定数字num在位图中的状态
        public void reverse(int num) {
            // 计算num对应的位在set数组中的位置
            // 使用位异或操作（^）反转该位的状态
            // 如果该位原来是0则变为1，原来是1则变为0
            set[num / 32] ^= 1 << (num % 32);
        }

        // 检查指定的数字num是否存在于位图中
        public boolean contains(int num) {
            // 计算num对应的位在set数组中的位置
            // 通过右移操作（>>）和位与操作（&）判断该位是否为1
            // 如果为1则表示num存在，返回true，否则返回false
            return ((set[num / 32] >> (num % 32)) & 1) == 1;
        }
    }

    // 对数器测试
    // 这个main方法用于测试Bitset类的功能是否正确
    // 通过与HashSet进行对比测试，在大量随机操作后检查两者结果是否一致
    public static void main(String[] args) {
        // 定义位图能够表示的数字范围的上限，这里是0到999
        int n = 1000;
        // 定义测试的次数
        int testTimes = 10000;
        System.out.println("测试开始");

        // 实现的位图结构
        Bitset bitSet = new Bitset(n);
        // 直接用HashSet做对比测试
        HashSet<Integer> hashSet = new HashSet<>();

        System.out.println("调用阶段开始");
        for (int i = 0; i < testTimes; i++) {
            // 生成一个0到1之间的随机数
            double decide = Math.random();
            // 生成一个0到n - 1之间的随机数，等概率得到
            int number = (int) (Math.random() * n);
            if (decide < 0.333) {
                // 以1/3的概率执行添加操作
                bitSet.add(number);
                hashSet.add(number);
            } else if (decide < 0.666) {
                // 以1/3的概率执行删除操作
                bitSet.remove(number);
                hashSet.remove(number);
            } else {
                // 以1/3的概率执行反转操作
                bitSet.reverse(number);
                if (hashSet.contains(number)) {
                    hashSet.remove(number);
                } else {
                    hashSet.add(number);
                }
            }
        }
        System.out.println("调用阶段结束");
        System.out.println("验证阶段开始");
        for (int i = 0; i < n; i++) {
            // 检查位图和HashSet对于每个数字的存在状态是否一致
            if (bitSet.contains(i)!= hashSet.contains(i)) {
                System.out.println("出错了!");
            }
        }
        System.out.println("验证阶段结束");
        System.out.println("测试结束");
    }
}